0% completed
Problem Statement
Given an array arr containing unique integers in the ascending order, and integer k, return the kth missing number starting from the arr[0].
The missing numbers are those that are not present in the array, and greater than arr[0].
Examples
-
Example 1:
- Input:
arr = [3, 5, 6, 7], k = 2 - Expected Output:
8 - Justification: The missing numbers in sequence are 4 and 8. The 2nd missing number is 8.
- Input:
-
Example 2:
- Input:
arr = [1, 2, 4, 8], k = 3 - Expected Output:
6 - Justification: The missing numbers are 3, 5, 6, etc. The 3rd missing number is 6.
- Input:
-
Example 3:
- Input:
arr = [2, 3, 4, 7, 8, 10, 11], k = 2 - Expected Output:
6 - Justification: The missing numbers in this sequence start from 5, 6, 9... The 2nd missing number in this sequence is 6.
- Input:
Solution
To solve this problem, we will use a binary search approach. This method is efficient because it significantly reduces the number of elements we need to inspect in the sorted array. By comparing the number of missing elements at the midpoint of the array with k, we can determine whether to search in the left or right half of the array.
This approach works effectively because the array is sorted, and we can calculate the number of missing elements up to any point. Since we're dealing with missing elements in a sequence, leveraging the sorted nature of the array allows us to quickly home in on the correct position, making this method both time-efficient and intuitive.
Step-by-step Algorithm
-
Initialize Variables:
- Set
nto the length of the input arraynums. - Initialize two pointers
left = 0andright = n - 1for binary search.
- Set
-
Perform Binary Search:
- While
leftis less thanright:- Calculate
midasright - (right - left) / 2. This finds the middle index betweenleftandright. - Check if the number of missing elements up to
midis less thank.- This is done by
nums[mid] - nums[0] - mid.
- This is done by
- If the missing count is less than
k, setlefttomid. This moves the search to the right half of the current segment. - Otherwise, set
righttomid - 1. This moves the search to the left half.
- Calculate
- While
-
Calculate and Return Result:
- After exiting the loop, calculate the k-th missing element as
nums[0] + k + left. - Return this value.
- After exiting the loop, calculate the k-th missing element as
Algorithm Walkthrough for Updated Example 3:
-
Input:
arr = [2, 3, 4, 7, 8, 10, 11], k = 2 -
Initialization:
n = 7(length of array)left = 0,right = 6
-
Binary Search Steps:
- Iteration 1:
mid = 6 - (6 - 0) / 2 = 3- Missing elements till
mid=arr[3] - arr[0] - (3 - 0) = 7 - 2 - 3 = 2 - Since Missing Count (2) is equal to
k, move right pointer:right = mid - 1 = 3 - 1 = 2
- Iteration 2:
mid = 2 - (2 - 0) / 2 = 1- Missing count =
arr[1] - arr[0] - (1 - 0) = 3 - 2 - 1 = 0 - Since Missing Count (1) is less than
k, move left pointer:left = mid = 1
- Iteration 3:
mid = 2 - (2 - 1) / 2 = 2 - 0 = 2- Missing count =
arr[2] - arr[0] - (2 - 0) = 4 - 2 - 2 = 0 - Since Missing Count (2) is less than
k, move left pointer:left = mid = 2
- Iteration 1:
-
Iteration 3:
- since left > right,
breakthe loop.
- since left > right,
-
Result Calculation:
- Exiting loop with
left = 2 - Calculate result:
nums[0] + k + left = 2 + 2 + 2 = 6
- Exiting loop with
-
Final Output:
6.
Code
Complexity Analysis
-
Time Complexity:
O(log n)- The algorithm uses binary search, dividing the array in half each step, leading to logarithmic time complexity.
-
Space Complexity:
O(1)- Only a constant amount of extra space is used in the algorithm, regardless of the input size.
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough for Updated Example 3:
Code
Complexity Analysis